#include <iostream>
#include <deque>
#include <cstdio>
#include <cstdlib>
using namespace std;

int n, m, D;
int c[100][100], a[100][100], d[100][101];
int usd, was[100][101], inf;

void load()
{
	scanf("%d%d%d", &D, &n, &m);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &a[i][j]);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &c[i][j]);
    inf = D + 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= n; j++)
        {
            d[i][j] = inf;
        }
}

deque <int> q;

void solve()
{
	for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < m; k++)
                c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
    
	q.clear();
	for (int i = 0; i < m; i++)
	{
		d[i][0] = 0;
		q.push_back(i * (n + 1));
	}
	int v;
	int res = inf;
	while (!q.empty())
	{
		v = q.front();
		q.pop_front();
		int i = v / (n + 1);
		int j = v - i * (n + 1);
		if (j == n)
		{
			res = min(res, d[i][j]);
			continue;
		}
		if (d[i][j] >= inf) continue;
		for (int k = 0; k < m; k++)
		{
			if (d[k][j + 1] > d[i][j] + a[k][j] + c[i][k])
			{
				d[k][j + 1] = d[i][j] + a[k][j] + c[i][k];
				if (rand() % 2 == 0)
					q.push_back(k * (n + 1) + j + 1);
				else q.push_front(k * (n + 1) + j + 1);
			}
		}
	}
	printf("%d\n", D - res);
}

int main()
{
//	freopen("gift.in", "rt", stdin);
//	freopen("gift.out", "wt", stdout);

	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		load();
		solve();
	}
	return 0;
}